A database system stores a collection of logically related data. A popular type of database system is the relational database management system (RDBMS), which stores relational tables made up of rows and columns. Each row represents an occurrence of an entity defined by a table, with an entity being a person, place, or thing about which the table contains information.
To extract data from, or to update, a relational table, queries according to a standard database query language (e.g., Structured Query Language or SQL) are used. Examples of SQL statements include INSERT, SELECT, UPDATE, and DELETE. The SELECT statement is used to retrieve information from the database and to organize information for presentation to a user or to an application program. The INSERT, UPDATE and DELETE statements specify other types of operations in a database system.
In many database operations, sorting is usually performed on records of one or more tables acted upon by a query. In performing such sorts, it is desirable to reduce the number of input/output (I/O) accesses that occur. I/O accesses are typically expensive in terms of the time required to perform each I/O access, and the physical resources that are consumed to perform the I/O access.
This is particularly a concern when large input files have to be sorted. To perform a sort of the records of an input file, the records are usually moved to temporary storage (e.g., cache) in a processing system. The temporary storage is usually much smaller (and faster) than persistent or main storage (e.g., hard disk drives or disk arrays). For sorts of large input files that are many times larger than the size of the temporary storage, a large number of I/O accesses are required to perform the sort (or other operation) by the processing system since records will have to be repeatedly moved between the temporary storage and persistent storage to perform the sort (or other operation). This may result in reduced efficiency and increased processing time of the database system when processing queries.